package Year22_Month05.day24;

import java.util.Arrays;

public class 堆排序 {
    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr){
        //当前size节用来向下调整获得大根堆
        int size = arr.length;
        for (int i = (size - 1)/ 2; i >= 0; i--) {
            //首先进行一个堆的调整，使得当前堆为大根堆
            shiftDown(arr,size,i);
        }
        //当前end用来进行堆排序,要实时更新end的值
        //其实主要思想就是建立大根堆之后不断交换根节点和最后一个节点，然后不断缩小end的值
        int end = size - 1;
        while (end > 0){
            swap(arr,0,end);
            shiftDown(arr,end,0);
            end--;
        }
    }

    public static void shiftDown(int[] arr,int size,int parent){
        int child = parent * 2 + 1;//这是左孩子
        while(child < size){
            //进行判断：左右孩子哪个大，哪个就用来交换
            if(child + 1 < size && arr[child + 1] > arr[child]){
                child = child + 1;
            }
            //如果说孩子的值大于父值，那就交换值，然后更新parent的节点值
            if(arr[child] > arr[parent]){
                swap(arr,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
